//
// Description: 138. 复制带随机指针的链表
// Created by Loading on 2021/7/22.
//

#include <bits/stdc++.h>
#include "Data_Structure_Definition.h"

using namespace std;

// 缓存复制的节点
unordered_map<Node *, Node *> catchNodes;

/* 哈希 + 递归回溯 */
Node *copyRandomList_BackTracking(Node *head) {
    if (!head) {
        return nullptr;
    }
    // 节点未被复制过
    if (!catchNodes.count(head)) {
        // 复制新节点
        catchNodes[head] = new Node(head->val);
        // 回溯查询 next 和 random 指针
        catchNodes[head]->next = copyRandomList_BackTracking(head->next);
        catchNodes[head]->random = copyRandomList_BackTracking(head->random);
    }
    return catchNodes[head];
}

/* 节点拆分 */
Node *copyRandomList(Node *head) {
    if (!head) {
        return nullptr;
    }

    // 每个节点后复制一个值相同的节点连接
    for (auto node = head; node; node = node->next->next) {
        Node *nodeNew = new Node(node->val);
        nodeNew->next = node->next;
        node->next = nodeNew;
    }

    Node *headNew = head->next;
    // 复制 random 指针
    for (auto node = head; node; node = node->next->next) {
        node->next->random = node->random ? node->random->next : nullptr;
    }

    // 连接复制的节点
    for (auto node = head; node; node = node->next) {
        Node *nodeNew = node->next;
        node->next = node->next->next;
        nodeNew->next = nodeNew->next ? nodeNew->next->next : nullptr;
    }

    return headNew;
}

int main() {
    Node *head = new Node(3);
    head->next = new Node(3);
    head->next->next = new Node(3);

    head->random = nullptr;
    head->next->random = head;
    head->next->next->random = nullptr;

    Node *res = copyRandomList(head);

    if (res) {
        cout << res->val << endl;
        if (res->next) {
            cout << res->next->val << endl;
        } else {
            cout << "nullptr" << endl;
        }

        if (res->random) {
            cout << res->random->val << endl;
        } else {
            cout << "nullptr" << endl;
        }
    } else {
        cout << "nullptr" << endl;
    }
}